#include <stdio.h>
#include "common_list.h"

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *fast = head, *slow = head;
    while(1) {
        // 这里不要再while条件判断里使用fast或者fast->next作为终止条件，可以避免在while结束后，还要再次判断是否要return
        if (!fast || !fast->next)
            return NULL;
        fast = fast->next->next;
        slow = slow->next;

        if (fast == slow)
            break;
    }

    fast = head;
    while (fast != slow) {
        fast = fast->next;
        slow = slow->next;
    }
    return fast;
}

int main(void)
{
    printf("#142. 环形链表 II (返回入环的点)\n\n");
    printf("O -> O -> O -> O -> # -> # -> # -> @ \n");
    printf("                    \\             / \n");
    printf("                     @  <- @  <- @ \n\n");
    printf("采用，快慢指针，快指针速度为慢指针2倍，两个第一次相遇在第一个@点，其中第一个#为入环点\n\n");
    printf("2 * (O + #) = O + # + @ + #\n");
    printf("2O + 2# = O + @ + 2#\n得O = @\n\n");
    printf("所以，当相遇后，fast节点重新置为head，\n然后fast和slow开始相同速度走，2个都走了O的距离，并再次在入环点(第一个#)相遇\n");

    struct ListNode *head = generate_cycle_list(10, 3);
    print_list(head);
    head = detectCycle(head);
    printf("point of entering cycle: %d\n", head ? head->val: -1);
    return 0;
}